It is well known to use a digital signature to provide a non-repudiable indication of the originator of a document (or other data) covered by the signature. Typically, the signature creation and verification processes involve a public/private key pair of the signer, the private key being used in creating the signature and the corresponding public key in the verification process.
An example digital signature is the Schnorr signature as described in the paper: “Efficient signature generation by smart cards” C. Schnorr., in Journal of Cryptology, 4(3):161-174, 1991. According to this signature scheme, there are two large primes p and q selected such that q|p−1, which are published with an element g of (Z/pZ)* of order q. A signer with private key x and public key gx mod p signs a message Mas follows:                The signer chooses a random number tεZ*q;        The signer computes:h=Hash(gt mod p∥M)s=t−xh mod q                     where ∥ represents concatenation                        The signer outputs (s, h) as its signature on message M        
Verification that the signature is from the sender and is on message M is effected by a verifier (who knows the signer's public key gx mod p) by seeking to generate a value h′ that should match the value of h in the signature. The verifier does this as follows:                The verifier first computes:(gt)′=gs(gx)h mod p                     where s and h are the received signature values (it being appreciated that if the values are correct, the right-hand expression is equivalent to gt mod p)                        The verifies then computes:h′=Hash((gt)′ mod p∥M)                    where M is the received message                        The verifier then compares h′ and h which, if equal proves that the message M was signed by the party having the public key gx mod p.        
Electronic transactions frequently involve the exchange of signatures on data representing commitments of the parties concerned. There is, however, an inherent problem of fairness in the sense that one party will be the first to provide their signature and this can be abused by the second party to the transaction. Thus, for example, the second party, being in possession of the first party's signature on some commitment, can represent to an independent party that the transaction has been completed by the second party having made a complimentary commitment to the first party when, in reality, this has not been done.
The problem of fair commitment or fair exchange of signatures is a fundamental problem in secure electronic transactions, especially where the parties involved are mutually distrustful. Up to now, there have been two different approaches to solving the problem of
exchanging signatures so that it is fair for both parties.
The first method involves the use of a (semi-trusted) arbitrator (Trent) who can be called upon to handle disputes between signers. The idea is that Alice registers her public key with Trent in a one-time registration, and thereafter may perform many fair exchanges with various other entities. Trent may possibly learn some part of Alice's secret at this stage. To take part in a fair exchange with Bob, Alice creates a partial signature which she sends to Bob. Bob can be convinced that the partial signature is valid (perhaps via a protocol interaction with Alice) and that Trent can extract a full binding signature from the partial signature. However, the partial signature on its own is not binding for Alice. Bob then fulfils his commitment by sending Alice his signature, and if valid, Alice releases the full version of her signature to Bob. The protocol is fair since if Bob does not sign, Alice's partial signature is worthless to Bob, and if Bob does sign but Alice refuses to release her full signature then Bob can obtain it from Trent. So the arbiter Trent may only be required in case of dispute (these are commonly referred to as optimistic fair exchange protocols), but a certain amount of trust still has to be placed in Trent. However, the main problem that remains with such a scheme is that in general, appropriate arbitor are simply not available. Further details and references of such schemes can be found in the article “Breaking and Repairing Optimistic Fair Exchange from PODC 2003” Y. Dodis, and L. Reyzin, in ACM Workshop on Digital Rights Management (DRM), October 2003.
The other common method of solving the problem of fair exchange of signatures is the idea of timed release or timed fair exchange of signatures in which the two parties sign their respective messages and exchange their signatures little by little. There are various problems with this approach. The first is that the protocol is highly interactive with many message flows. The second is that one party, say Bob, may often be at an advantage in that he sometimes has (at least) one more bit of Alice's signature than she has of his. This may not be significant if the computing resources of the two parties are roughly equivalent, but if Bob has superior computing resources, this may put Bob at a significant advantage over Alice since Bob may terminate the protocol early and use his resources to compute the remainder of Alice's signature, while it may be infeasible for Alice to do the same. There are methods to reduce this type of problem which involve the use of special “timing” functions, but even if the fairness of the protocol is guaranteed by such methods, it is still too interactive for many applications. Further details and references for such schemes can be found in the paper “Timed Fair Exchange of Standard Signatures” J. Garay, and C. Pomerance in Proceedings Financial Crypto '03.
It may further be noted that the problem of avoiding one party's signature being abused by presentation to another party to prove some commitment by the first party to a non-existent transaction, can be avoided by use of a signature that can only be verified by a designated party (such as the other party in a transaction). Such a signature scheme (referred to as a Designated Verifier signature scheme) is described in the paper “Designated verifier proofs and their applications” M. Jakobsson, K. Sako and R. Impagliazzo in Lecture Notes in Computer Science 1996, vol 1070. Signatures of this type are ambiguous in that it is not possible for a party, who is not the signer or the designated verifier, to tell which of the signer or the designated verifier has created the signature. More particularly, in the implementation described in the above-referenced paper, the signatures are based on Schnorr signatures with the signer creating its signature using their own private key and the public key of the designated verifier. The designated verifier can produce an alternate signature on the same message using the verifier's own private key and the public key of the signer. The nature of these signatures is such that the verification operation as operated by a signature-checking party who is not the signer or designated verifier cannot tell whether a particular signature is one produced by the signer or is, in fact, a corresponding alternate signature produced by the designated verifier. Thus, whilst the designated verifier can prove that a signature created by the signer was so created (because the designated verifier knows that he did not), the designated verifier cannot prove this to an independent signature-checking party.
Another technique which was designed for different purpose but offers the same ambiguity property is ring signatures. A ring signature convinces an external verifier that a message has been signed by one of a number of possible independent signers without allowing the verifier to identify which signer it was. A 1-out-of-2 ring signature has all the security features of the designated verifier signature with one signer and one designated verifier. Further details and references of ring signature schemes can be found in the articles “How to leak a secret” R. Rivest, A. Shamir and Y. Tauman, in Advances in Cryptology—Asiacrypt 2001, LNCS 2248, pages 552-565, Springer 2001; and “1-out-of-n signatures from a variety of keys” M. Abe, M. Ohkubo and K. Suzuki, in Cryptology—Asiacrypt 2002, LNCS 2501, pages 415-432, Springer 2002.
It is an object of the present invention to provide a signature scheme for transactions that is fair. It is a more general object of the invention to provide a signature that is ambiguous until determined otherwise by the signer.